
/**
 * @param {string} str
 * @description 根据 str 生成所有可能顺序的字符串, 使用动态规划解答
 * @return {array} resultArr 所有字符串组成的数组
 */
function getAllOrderString (str) {
  const len = str.length
  if (len === 1) { // 递归结束条件
    return [str]
  }
  // 递归体
  let resultArr = []
  const preArr = getAllOrderString(str.slice(0, len - 1))
  preArr.map((item) => {
    resultArr = resultArr.concat(getInsertStrArr(str[len - 1], item))
  })
  return resultArr
}

/**
 * @description 求 item 插入 str 中组成的新字符串
 * @param {string} item
 * @param {string} str
 * @returns {array} arr
 */
function getInsertStrArr (item, str) {
  const arr = []
  for (let i = 0; i <= str.length; i++) {
    arr.push(str.slice(0, i) + item + str.slice(i))
  }
  return arr
}

// 测试代码
console.log('test1:', getAllOrderString('12'))
console.log('test2:', getAllOrderString('123'))
